#include <iostream>
using namespace std;

struct node
{ int info;
  node *next;
};

struct List
{ node *first;
  node *last;
  List()
  { first=last=NULL; }
};
    
void push_front(List &L, int x)
{ node *t = new node;
  t->info = x;
  t->next = L.first;
  L.first = t;
  if(L.last==NULL) L.last=t;
}   
  
void push_back(List &L, int x)
{ node *t = new node;
  t->info = x;
  t->next = NULL;
  if(L.last==NULL) L.first=L.last=t;
  else { L.last->next = t; L.last=t;  }  
}

void show_list(List L)
{ node *p=L.first;
  while(p!=NULL)
  { cout << p->info << " ";
    p = p->next;
  }
  cout << endl;
}    
  

List L1, L2, R;


int main()
{ 
  
  push_front(L1,50);
  push_front(L1,40);
  push_back(L1,56);
  
  push_front(L2,34);
  push_back(L2,45);
  push_front(L2,30);
  push_front(L2,20);
  
  show_list(L1);
  show_list(L2);
  cout << "------" << endl;
  
  node *p=L1.first, *q=L2.first; 
  while(p!=NULL && q!=NULL)
  { if(p->info <= q->info)
    { push_back(R,p->info); p = p->next; }
    else
    { push_back(R,q->info); q = q->next; }
  }   
    
  while(p!=NULL)
  { push_back(R,p->info); p = p->next; }
    
  while(q!=NULL)
  { push_back(R,q->info); q = q->next; }
    
    
  show_list(L1);
  show_list(L2);
  
  show_list(R);  
    
     
  return 0;
}    
